# !/usr/bin/env python
# -*- coding: utf-8 -*-

# 给你一个字符串 s，找到 s 中最长的回文子串。
#
# 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
#
#  
#
# 示例 1：
#
# 输入：s = "babad"
# 输出："bab"
# 解释："aba" 同样是符合题意的答案。
# 示例 2：
#
# 输入：s = "cbbd"
# 输出："bb"
#  
#
# 提示：
#
# 1 <= s.length <= 1000
# s 仅由数字和英文字母组成
#
# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/longest-palindromic-substring
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    # 中心扩展算法
    # 时间复杂度O(n^2), 空间复杂度O(1)
    def longestPalindrome(self, s: str) -> str:
        ss = ""
        length = len(s)
        for i in range(0, length):
            m = i - 1
            n = i + 1
            while n < length or m >= 0:
                flag = True
                if m >= 0 and s[m] == s[i]:
                    m -= 1
                    flag = False
                if n < length and s[n] == s[i]:
                    n += 1
                    flag = False
                if flag:
                    break

            while n < length and m >= 0:
                if s[m] == s[n]:
                    m -= 1
                    n += 1
                else:
                    break
            if len(ss) < (n - m - 1):
                ss = s[m + 1: n]
        return ss

    # 动态规划
    def longestPalindrome2(self, s: str) -> str:
        pass


if __name__ == '__main__':
    s = Solution()
    print(s.longestPalindrome("babad"))
    print(s.longestPalindrome("cbbd"))
    print(s.longestPalindrome("bb"))
    print(s.longestPalindrome("aaaa"))
